package Association_rules;

import weka.associations.FPGrowth;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.*;
import java.util.ArrayList;
import java.util.List;

public class FP_growth {

    private final static double SUPPORT = 0.1; // 支持度阈值
    private final static double CONFIDENCE = 0.7; // 置信度阈值
    private final static String ITEM_SPLIT = " "; // 项之间的分隔符
    private final static String CON = "==>"; // 项之间的分隔符
    private static int size,total_size;
    private String strings="";

    public void FP_tree(ArrayList<String> dataList){
        Tree<String> strTree;
        List<Map.Entry<String,Integer>> list;
        list=findFrequentOneSets(dataList);
        for(int i=0;i<list.size();i++){
            System.out.println(list.get(i).getKey()+"个数统计： "+list.get(i).getValue());
        }
        for(int i=0;i<size;i++){
            if(1.0*list.get(i).getValue()/total_size<SUPPORT){
                list.remove(i);
                this.size--;
            }
        }
        Node<String> []Node_list = new Node[size];
        strTree=creat_tree(dataList,list);
        for(int i=0;i<size;i++){
            Node_list[i]=new Node<String>(list.get(i).getKey());
            Node_list[i].setCount(0);
        }
        Node_list=creat_list(Node_list,strTree.getRoot());
        strTree.getRoot().setCount(dataList.size());
        FPgrowth(strTree,Node_list);
    }

    private List<Map.Entry<String,Integer>> findFrequentOneSets(ArrayList<String> dataList)
    {
        Map<String, Integer> resultSetMap = new HashMap<>();
        for(String data:dataList)
        {
            String[] strings = data.split(ITEM_SPLIT);
            for(String string:strings)
            {
                string += ITEM_SPLIT;
                if(resultSetMap.get(string)==null)
                {
                    resultSetMap.put(string, 1);
                }
                else {
                    resultSetMap.put(string, resultSetMap.get(string)+1);
                }
            }
        }
        List<Map.Entry<String,Integer>> list = new ArrayList<Map.Entry<String,Integer>>(resultSetMap.entrySet());
        Collections.sort(list, new Comparator<Map.Entry<String, Integer>>() {
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                return (o2.getValue() - o1.getValue());
            }
        });
        this.size=list.size();
        this.total_size=dataList.size();
        return list;
    }

    public Tree<String> creat_tree(ArrayList<String> dataList,List<Map.Entry<String,Integer>> list){
        Tree<String> strTree=new Tree<String>(new Node<String>("FP-growth树根节点"));
        strTree.getRoot().setCount(0);
        Node<String> result=strTree.getRoot(),tempNode;
        int parameter,flag=0,count;
        for(String data:dataList) {
            parameter=1;
            String[] strings = data.split(ITEM_SPLIT);
            String strings2;
            for(int i=0;i<size;i++){
                for(int j=0;j<strings.length;j++){
                    strings2 = strings[j] +ITEM_SPLIT;
                    if(list.get(i).getKey().compareTo(strings2)==0) {
                        for (flag = 0, count = 0; count < result.getNodeList().size(); count++) {
                            if (result.getNodeList().get(count).getCont().compareTo(strings2)==0) {
                                parameter+=1;
                                result = result.getNodeList().get(count);
                                result.addCount(1);
                                flag = 1;
                                break;
                            }
                        }
                        if (flag == 0) {
                            parameter+=1;
                            tempNode= new Node<String>(strings2);
                            tempNode.setDepth(parameter);
                            strTree.addNewNode(result, tempNode);
                            result=tempNode;
                        }
                        break;
                    }
                }
            }
            result=strTree.getRoot();
        }
        return strTree;
    }

    public Node<String>[] creat_list(Node<String>[] Node_list,Node<String> root){
        for(Node<String> tempNode:root.getNodeList()){
            for(int i=size-1;i>=0;i--){
                if(Node_list[i].getCont().compareTo(tempNode.getCont())==0){
                    Node_list[i].addCount(tempNode.getCount());
                    Node_list[i].setParent(root);
                    Node_list[i].nodeList.add(tempNode);
                }
            }
            Node_list=creat_list(Node_list,tempNode);
        }
        return Node_list;
    }

    public void FPgrowth(Tree<String> strTree,Node<String>[] Node_list){
        Integer count,flag;
        Node<String> tempNode=strTree.getRoot();
        if(tempNode.nodeList.size()==1){
            String []strings2=this.strings.split(ITEM_SPLIT);
            for(String strings1="";tempNode.nodeList.size()==1;tempNode=tempNode.nodeList.get(0)){
                strings1+=tempNode.nodeList.get(0).getCont();
                Double confidence=tempNode.nodeList.get(0).getCount()*1.0/tempNode.getCount();
                if(confidence>CONFIDENCE){
                    System.out.println(this.strings+strings1+"支持度: "+confidence+"\n");
                    tempNode=tempNode.nodeList.get(0);
                    this.strings+=tempNode.getCont();
                }
                if(tempNode.nodeList.size()==0){
                    break;
                }
            }
            this.strings="";
            for(int i=0;i<strings2.length-1;i++){
                this.strings+=(strings2[i]+ITEM_SPLIT);
            }
        }else{
            for(Integer i=Node_list.length-1;i>0;i--){
                Node<String>[] Node_statistic=new Node[i+1];
                for(Integer k=0;k<i;k++){
                    Node_statistic[k]=new Node<String>(Node_list[k].getCont());
                    Node_statistic[k].setCount(0);
                }
                for(Integer j=0,m=0;j<Node_list[i].nodeList.size();j++) {
                    Node<String> FP_Node;
                    FP_Node=Node_list[i].nodeList.get(j);
                    count=FP_Node.getCount();
                    while(FP_Node.getParent()!=null){
                        for(int k=0;k<i;k++){
                            if(Node_statistic[k].getCont().compareTo(FP_Node.getCont())==0){
                                Node_statistic[k].addCount(count);
                                for(m=0;m<Node_statistic[k].nodeList.size();m++) {
                                    if(FP_Node.getParent().hashCode()==Node_statistic[k].nodeList.get(m).getParent().hashCode()) {
                                        break;
                                    }
                                }
                                if((m==Node_statistic[k].nodeList.size())||(Node_statistic[k].nodeList.size()==0)) {
                                    Node_statistic[k].nodeList.add(FP_Node);
                                }
                            }
                        }
                        FP_Node=FP_Node.getParent();
                    }
                }
                flag=i;
                for(int k=0;k<i;k++){
                    if((1.0*Node_statistic[k].getCount()/total_size)<SUPPORT){
                        Node_statistic[k].setCount(0);
                        flag--;
                    }
                }
                Node_statistic[i]=Node_list[i];
                if(flag!=0){
                    Node<String>[] Node_child_tree=new Node[flag];
                    for(int j=0,parameter=0;j<i;j++){
                        if(Node_statistic[j].getCount()!=0){
                            Node_child_tree[parameter]=Node_statistic[j];
                            parameter++;
                        }
                    }
                    Tree<String> child_tree;
                    this.strings+=Node_list[i].getCont();
                    child_tree=child_FP_tree(Node_statistic,Node_list[i].getCount());
                    FPgrowth(child_tree,Node_child_tree);
                }
            }
        }
    }

    public Tree<String> child_FP_tree(Node<String>[] Node_list,int count){
        Node<String> stringNode,leaf_Node,tempNode,search_Node,add_Node;
        Integer counter,depth=0,flag,length=Node_list.length;
        Tree<String> child_tree=new Tree<String>(new Node<String>("FP-growth树根节点",count));
        add_Node=new Node<String>(Node_list[0].getCont(), Node_list[0].getCount(),2);
        child_tree.addNewNode(child_tree.getRoot(), add_Node);
        for(int i=1;i<length-1;i++) {
            if (Node_list[i].getCount() != 0) {
                for (int k = 0; k < Node_list[i].nodeList.size(); k++) {
                    leaf_Node = Node_list[i].nodeList.get(k);
                    tempNode = leaf_Node.getParent();
                    search_Node = search(tempNode, child_tree.getRoot());
                    flag=i+leaf_Node.depth;
                    counter=0;
                    for(int j=0,num;j<Node_list[length-1].nodeList.size();j++){
                        for(num=length-2;num>=0;num--){
                            stringNode=Node_list[length-1].nodeList.get(j).getParent();
                            if(Node_list[num].getCont().compareTo(stringNode.getCont())==0){
                                depth=stringNode.depth;
                                break;
                            }
                        }
                        if(((depth-num)==(leaf_Node.depth-i))&&(depth>=leaf_Node.depth)){
                            counter+=Node_list[length-1].nodeList.get(j).getCount();
                        }
                    }
                    add_Node = new Node<String>(leaf_Node.getCont(), counter,leaf_Node.depth);
                    if (add_Node.getCount() * 1.0 / total_size >= SUPPORT) {
                        child_tree.addNewNode(search_Node, add_Node);
                    }
                }
            }
        }
        return child_tree;
    }

    public Node<String> search(Node<String> tempNode,Node<String> rootNode){
        if((tempNode.getCont().compareTo(rootNode.getCont())!=0)||(tempNode.depth!=rootNode.depth)){
            for(Node<String>search_node:rootNode.getNodeList()){
                rootNode=search(tempNode,search_node);
            }
        }
        return rootNode;
    }

    public static void main(String[] args) throws Exception{
        ArrayList<String> dataList = new ArrayList<>();
        String fn=("/home/tang/basket.txt");
        File file=new File(fn);
        FileReader fr=new FileReader(file);
        BufferedReader br=new BufferedReader(fr);
        String line;
        while((line=br.readLine())!=null){
            dataList.add(line);
        }
        System.out.println("==========数据集合==========");
        for(String string:dataList)
        {
            System.out.println(string);
        }
        System.out.println("==========频繁项集==========");
        FP_growth FP_growth2 = new FP_growth();
        FP_growth2.FP_tree(dataList);
    }
}
